package cn.yoaket.algorithm;


import cn.yoaket.unit.Edge;
import cn.yoaket.unit.Point;

import java.util.*;

public class AStar {


    public static Edge execute(Point start, Point goal, List<Edge> edges) {
        Edge path;
        //将路网最近点作为起点的周边点
        boolean startFlag = nearest(start, edges);
        boolean foalFlag = nearest(goal, edges);

        path = path(start, goal,edges);

        //将添加到路网上的多余的点和多余的周边点删除,防止影响下一次检索
        remove(start, startFlag);
        remove(goal, foalFlag);

        return path;
    }

    static double getRation(Point a, Point b, List<Edge> edges){
        for (Edge edge : edges) {
            if(edge.contains(a) && edge.contains(b))
                return edge.getRatio();
        }
        return 0;
    }

    private static void remove(Point goal, boolean flag) {
        if (flag) {
            for (Point point : goal.near) {
                point.near.remove(goal);
                for (Point near : point.near) {
                    near.near.remove(point);
                }
            }
        } else {
            for (Point point : goal.near) {
                point.near.remove(goal);
            }
        }
    }

    //找到点到一条线段的最近路线
    static Point getVer(Point pt, Point begin, Point end) {

        Point retVal = new Point();
        double dx = begin.getX() - end.getX();
        double dy = begin.getY() - end.getY();
        if (Math.abs(dx) < 0.00000001 && Math.abs(dy) < 0.00000001) {
            retVal = begin;
            return retVal;
        }

        double u = (pt.getX() - begin.getX()) * (begin.getX() - end.getX()) +
                (pt.getY() - begin.getY()) * (begin.getY() - end.getY());
        u = u / ((dx * dx) + (dy * dy));

        //如果垂足不在线段上就返回null
        if (u > 0)
            return begin;
        else if (u < -1)
            return end;
        retVal.setLocation(begin.getX() + u * dx, begin.getY() + u * dy);
        return retVal;
    }


    //找到路网的最短距离,并返回点
    static boolean nearest(Point local, List<Edge> edges) {
        //使用flag来表示点是否是新增加的
        boolean flag = false;
        Point target = null;
        double dis = Double.MAX_VALUE;
        Point begin = null;
        Point end = null;

        for (Edge e : edges) {
            for (int i = 0; i < e.size() - 1; ++i) {
                Point vertical = getVer(local, e.get(i), e.get(i + 1));
                if (distance(vertical, local) < dis) {
                    target = vertical;
                    dis = distance(target, local);
                    begin = e.get(i);
                    end = e.get(i + 1);
                }
            }
        }
        assert target != null;

        //关联鼠标点和最近点
        target.add(local);
        local.add(target);

        //如果点原本不存在,还需要关联点和其左右点
        if (target != begin && target != end) {
            begin.add(target);
            end.add(target);
            target.add(begin);
            target.add(end);
            flag = true;
        }
        return flag;
    }

    static boolean isNear(Point a,Point b){
        return Math.abs(a.getX() - b.getX()) < 0.1 && Math.abs(a.getY() - b.getY()) < 0.1;
    }

    //设置所有点的周边的点
    public static void setNear(List<Edge> edges) {
        List<Point> points = new ArrayList<>();
        for (Edge e : edges) {
            for (int i = 0; i < e.size(); ++i) {
                if (i > 0)
                    e.get(i).add(e.get(i - 1));
                if (i < e.size() - 1)
                    e.get(i).add(e.get(i + 1));
                points.add(e.get(i));
            }
        }

        for (Point p1 : points) {
            for (Point p2 : points) {
                if (p1 != p2 && isNear(p1,p2))
                    p1.near.addAll(p2.near);
            }
        }

    }

    //曼哈顿距离
//    static double distance(Point a, Point b){
//        return Math.abs(a.getX()-b.getX()) + Math.abs(a.getY()-b.getY());
//    }


    //欧式距离
    static double distance(Point a, Point b) {
        return Math.sqrt(Math.pow(a.getX() - b.getX(), 2) + Math.pow(a.getY() - b.getY(), 2));
    }

    //得到两点之间的代价
    static double cost(Point a, Point b) {
        return distance(a, b);
    }

    //获得图上两点的最短的路径
    static Edge path(Point start, Point goal,List<Edge> edges) {

        //代价队列
        PriorityQueue<Point> frontier = new PriorityQueue<>();
        //已被访问点队列
        Set<Point> visited = new HashSet<>();

        //初始化起点
        start.steps = 0;
        start.setCost(0);
        start.pre = null;
        frontier.add(start);

        //得到的最短路径
        Edge shortestPath = new Edge();
        Point p = null;

        while (!frontier.isEmpty()) {
            //取出第一个元素,并设置已访问
            Point cur = frontier.poll();
            visited.add(cur);

            //如果第一个点是终点退出循环
            if (cur.equals(goal)) {
                p = cur;
                break;
            }

            //遍历第一个点周边的点,并将未访问的点添加到代价队列
            for (Point near : cur.near) {
                if (visited.contains(near))
                    continue;
                near.pre = cur;

                near.steps = near.pre.steps + cost(near, near.pre);

                //定义一个代价函数的计算方式 : 总体1 可调整
                near.setCost(near.steps + cost(near, goal));
//                near.setCost(near.pre.steps + (1 - getRation(near,near.pre,edges)) * cost(near, near.pre) + cost(near, goal));
                frontier.add(near);
            }
        }

        //根据pre指针取出最短路径
        while (p != null) {
            shortestPath.add(p.getX(), p.getY());
            p = p.pre;
        }

        return shortestPath;
    }

}
